package com.myhome.money.base.datastructure;

import java.util.Random;

/**
 * @Author: 许路路
 * @Date: 2019/4/15
 */
public class Arrays {

    /**
     * 1、实现一个支持动态扩容的数组--有序数组的插入
     * 可以参考ArrayList的实现
     *
     * @param value
     */
    public static void insert(int[] arr1, int value) {
        if (arr1 == null || arr1.length == 0) {
            arr1 = new int[1];
            arr1[0] = value;
            return;
        }
        int[] arr3 = new int[arr1.length + 1];
        //把原数组赋值到新数组
        boolean isInsert = false;
        for (int i = 0, j = 0; i < arr1.length + 1; i++) {
            if (j == arr1.length) {
                arr3[i] = value;
                break;
            }
            if (isInsert || value > arr1[j]) {
                arr3[i] = arr1[j];
                j++;
            } else {
                isInsert = true;
                arr3[i] = value;
            }
        }
        arr1 = arr3;
        print(arr1);
        System.out.println("==============================");
    }

    /**
     * 3、实现两个有序数组合并为一个有序数组
     *
     * @param arr1
     * @param arr2
     */
    public static void arrayMerge(int[] arr1, int[] arr2) {
        if (arr1 == null || arr1.length == 0) {
            print(arr2);
            return;
        }
        if (arr2 == null || arr2.length == 0) {
            print(arr1);
            return;
        }
        int length = arr1.length + arr2.length;
        int[] arr = new int[length];
        int i = 0, j = 0, k = 0;
        while (i <= arr1.length && j <= arr2.length) {
            if (i == arr1.length) {
                while (j < arr2.length) {
                    arr[k++] = arr2[j++];
                }
                break;
            }
            if (j == arr2.length) {
                while (i < arr1.length) {
                    arr[k++] = arr1[i++];
                }
                break;
            }
            if (arr1[i] <= arr2[j]) {
                arr[k++] = arr1[i++];
            } else {
                arr[k++] = arr2[j++];
            }
        }
        print(arr);
    }

    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {3, 8, 9, 34, 54, 67, 78, 88};
        int[] arr2 = {3, 7, 11, 22, 33, 44, 55, 66, 77};
        for (int i = 0; i < 5; i++) {
            Random random = new Random();
            insert(arr1, random.nextInt(100));
        }
        System.out.println("3.=================================");
        arrayMerge(arr1, arr2);
    }


    /**
     * 2、实现一个大小固定的有序数组，支持动态增删改查操作
     */
    class FixedSizeArray {
        int[] data;

        public void add() {

        }

        public void remove() {

        }

        public void set(int index, int value) {

        }

        public int get(int index) {
            return 0;
        }

    }

}
